// 74.搜索二维矩阵
package LeetcodeHot100;

public class Solution074 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (target < matrix[0][0])
            return false;
        int left = 0;
        int right = matrix.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] == target)
                return true;
            else if (matrix[mid][0] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        for (int i = 1; i < matrix[0].length; i++) {
            if (matrix[left - 1][i] == target)
                return true;
        }
        return false;
    }
}
